#define _CRT_SECURE_NO_WARNINGS 1

#include <Windows.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct QNode
{
    int x;
    struct QNode* next;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
}Queue;

void QueueInit(Queue* pq)
{
    if (pq == NULL)
        return;
    pq->head = NULL;
    pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
    if (pq == NULL)
        return;
    pq->tail = NULL;
    while (pq->head != NULL)
    {
        QNode* cur = pq->head->next;
        free(pq->head);
        pq->head = cur;
    }
}
QNode* _CreateQNode(int x)
{
    QNode* node = (QNode*)calloc(1, sizeof(QNode));
    node->x = x;
    node->next = NULL;
    return node;
}
void QueuePush(Queue* pq, int x)
{
    if (pq == NULL)
        return;
    QNode* node = _CreateQNode(x);
    if (pq->head == NULL)
        pq->head = pq->tail = node;
    else
    {
        pq->tail->next = node;
        pq->tail = node;
    }
}
void QueuePop(Queue* pq)
{
    if (pq == NULL)
        return;
    if (pq->head == NULL && pq->tail == NULL)
        return;
    QNode* node = pq->head;
    pq->head = pq->head->next;
    free(node);
    if (pq->head == NULL)
        pq->tail = NULL;
}
int QueueFront(Queue* pq)
{
    if (pq == NULL)
        return;
    if (pq->head == NULL && pq->tail == NULL)
        return;
    return pq->head->x;
}
int QueueBack(Queue* pq)
{
    if (pq == NULL)
        return;
    if (pq->head == NULL && pq->tail == NULL)
        return;
    return pq->tail->x;
}
_Bool QueueEmpty(Queue* pq)
{
    if (pq == NULL)
        return;
    return (pq->tail == NULL && pq->head == NULL);
}
int QueueSize(Queue* pq)
{
    if (pq == NULL)
        return;
    int count = 0;
    QNode* cur = pq->head;
    while (cur)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

typedef struct
{
    Queue q1;
    Queue q2;
}MyStack;


MyStack* myStackCreate()
{
    MyStack* ms = (MyStack*)calloc(1, sizeof(MyStack));
    QueueInit(&ms->q1);
    QueueInit(&ms->q2);
    return ms;
}

void myStackPush(MyStack* obj, int x)
{
    Queue* ful = &obj->q1;
    if (QueueEmpty(ful))
        ful = &obj->q2;
    QueuePush(ful, x);
}

int myStackPop(MyStack* obj)
{
    Queue* emp = &obj->q1, * ful = &obj->q2;
    if (!QueueEmpty(emp))
        emp = &obj->q2, ful = &obj->q1;
    while (QueueSize(ful) > 1)
    {
        QueuePush(emp, QueueFront(ful));
        QueuePop(ful);
    }
    int ret = QueueFront(ful);
    QueuePop(ful);
    return ret;
}

int myStackTop(MyStack* obj)
{
    Queue* ful = &obj->q1;
    if (QueueEmpty(ful))
        ful = &obj->q2;
    return QueueBack(ful);
}

bool myStackEmpty(MyStack* obj)
{
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

int main()
{
    MyStack* test = myStackCreate();
    for (int i = 1; i <= 10; i++)
        myStackPush(test, i);
    while (!myStackEmpty(test))
        printf("%d ", myStackPop(test));
    printf("\n");
    myStackFree(test);
	return 0;
}